import java.util.*;
public class Practice2{
    //https://ac.nowcoder.com/acm/problem/50039
    //这题考数学, 组合题, 但是INF有点傻逼, 看成1e9调试了半天
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int INF = 109;
        int sum = n;
        for(int i = 0;i < m - 1;i++){
            sum *= (n - 1);
            sum %= INF;
        }
        System.out.println(sum);
    }
}